package util;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.SortedSet;
import java.util.TreeSet;

public class LSortedSet<T> {

	// maps operand to an index of a sorted set in the list
	public Map<T, SortedSet<T>> map;

	private Comparator<T> comp;

	/**
	 * 
	 * @param comp
	 */
	public LSortedSet(Comparator<T> comp) {
		this(new HashMap<T, SortedSet<T>>(), comp);

	}

	/**
	 * 
	 * @param list
	 * @param map
	 * @param comp
	 */
	private LSortedSet(Map<T, SortedSet<T>> map, Comparator<T> comp) {
		this.map = map;
		this.comp = comp;
	}

	public void reset() {
		map = new HashMap<T, SortedSet<T>>();
	}


	public void remove(T o) {

		SortedSet<T> s = map.get(o);
		if(s != null) {
			s.remove(o);
			map.remove(o);
		}
	}


	/**
	 * 
	 * @param o
	 * @return
	 */
	public boolean contains(T o) {
		if(map.get(o) != null)
			return true;
		else 
			return false;
	}

	/**
	 * Create a new set with the values 'val1', 'val2'
	 * @param o1 first value in the set
	 * @param o2 second value in the set
	 */
	private void createSet(T o1, T o2) {

		TreeSet<T> set = new TreeSet<T>(comp);
		set.add(o1);
		set.add(o2);

		map.put(o1, set);
		map.put(o2, set);

	}

	public T getMin(T o) {
		SortedSet<T> set = map.get(o);
		if(set != null) {
			return set.first();
		}
		return null;
	}


	/**
	 * Append value to a set in the following way:
	 * 	if a none of them appears in our data, make a new set and put them there
	 * 	if src appears on our data, add dst to the same set
	 *  if dst appears on out data, remove it, because it has changed
	 *  if both appear in the same set return the first set element;
	 * @param o1 first value to insert
	 * @param o2 second value to insert
	 * @return
	 */
	public T appendToSet(T o1, T o2) {

		if(!contains(o1) && !contains(o2)) {
			createSet(o1, o2);

			//code.add(that);
			return null;

		}
		else if(contains(o1) && !contains(o2)) {
			SortedSet<T> set = map.get(o1);
			T equals = set.first();
			//System.out.println("+++++++" + equals  + "+++++++");
			set.add(o2);
			map.put(o2,set);

			return equals;
		}
		else if(!contains(o1) && contains(o2)) {
			//System.out.println(toString());

			remove(o2);
			//System.out.println(toString());
			createSet(o1, o2);
			//System.out.println(toString());
			return null;
		}
		else {
			//System.out.println("BOTH\n");
			//System.out.println(o1+":"+map.get(o1));
			//System.out.println(o2+":"+map.get(o2));

			if(map.get(o1).equals(map.get(o2))) { // in same set, just get minimum
				T equals = map.get(o1).first();

				return equals;
			}
			else { // merge two sets

				T equals = map.get(o1).first();

				SortedSet<T> rmvSet = map.get(o1);
				SortedSet<T> bigSet = map.get(o2);
				bigSet.addAll(rmvSet);

				for(T key : rmvSet) {
					map.put(key, bigSet);
				}

				rmvSet = null;

				return equals;
			}
		}


	}

	public String toString() {
		String s = "";


		s += "Map:\n====\n";
		for(T key : map.keySet()) {
			s += key.toString() + ":\n";
			for(T elem : map.get(key)) {
				s += "   "+elem + "\n";
			}
		}



		return s;
	}
}
